#include <stdio.h>
#include <stdlib.h>

// struct LinkList {
// } typedef LinkList;

struct LinkNode {
    int val;
    LinkNode* next;
} typedef LinkNode;

void printLinkList(LinkNode* head) {
    if (head == NULL) {
        printf("<NULL node>\n");
        return;
    }
    while (head->next != NULL) {
        printf(" -> %d", head->val);
        head = head->next;
    }
    printf("\n");
}

/**
 * 新创建一个节点，返回节点指针
 */
LinkNode* getNode(int n) {
    LinkNode* res = NULL;
    res = (LinkNode*)malloc(sizeof(*res));
    res->val = n;
    res->next = NULL;
    return res;
}

void delNode(LinkNode* node) {
    node->next = NULL;
    free(node);
    node = NULL;
}

/**
 * 输入很多个数字，获得一个链表，返回头节点
 */
LinkNode* inputLinkList() {
    LinkNode* node = getNode(-255);
    LinkNode* res = node;
    int len;
    printf("input a number as the link node length:");
    scanf("%d", &len);
    for (int i = 0; i < len; i++) {
        // 通过键盘输入的方式，赋值当前节点一个数字
        int num;
        scanf("%d", &num);
        node->val = num;
        // 新建一个下一个节点
        LinkNode* nextNode = getNode(0);
        // 讲当前节点的下一个节点接上新创建的节点
        node->next = nextNode;
        // node步进指针指向新创建的节点
        node = nextNode;
    }
    return res;
}

/**
 * P37 T1
 * 删除所有值为tar的节点，递归算法
 * 先做不递归的
 */
LinkNode* removeTar(LinkNode* head, int tar) {
    if (head == NULL) {
        return NULL;
    }
    // 还未处理左侧就是tar的情况
    LinkNode* left = head;
    while (left->next != NULL && left->val == tar) {
        left = left->next;
    }
    LinkNode* res = left;
    LinkNode* right = left->next;

    // 一左一右同时前进，右侧节点需要被删除，需要拨动左侧节点next属性
    while (right != NULL) {
        if (right->val == tar) {
            left->next = right->next;
            free(right);
            right = left->next;
        } else {
            left = left->next;
            right = right->next;
        }
    }
    return res;
}

/**
 * 删除所有值为tar的节点，递归算法
 * 有问题
 */
void removeTarDFS(LinkNode* curNode, int tar) {
    if (curNode == NULL) {
        return;
    }
    LinkNode* delNode;
    if (curNode->val == tar) {
        delNode = curNode;
        curNode = curNode->next;
        free(delNode);
        removeTarDFS(curNode, tar);
    } else {
        removeTarDFS(curNode->next, tar);
    }
}

/**
 * T3 反向打印
 * 有点bug，一开始会默认打一个0出来
 */
void printReversDFS(LinkNode* curNode) {
    if (curNode == NULL) {
        printf("NULL\n");
        return;
    } else {
        printReversDFS(curNode->next);
        printf("%d %p\n", curNode->val, curNode);
    }
}

/**
 * 翻转单链表
 */
void reverseNode(LinkNode* head) {
    LinkNode* n1 = head;
    LinkNode* n2 = head->next;
}